package leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * Created by Ghost on 2014/10/9 0009.
 */
public class Word_Break {

    public boolean wordBreak(String s, Set<String> dict) {
        boolean[] w = new boolean[s.length()+1];
        w[0]=true;
        int size = s.length();
        for(int i=0;i<size;i++){
            if(dict.contains(s.substring(0,i+1))){
                w[i+1] = true;
            }
            else{
                if(i==0){
                    w[i+1] = dict.contains(s.substring(i,i+1));
                }

                else{
                    for(int j=i;j>=0;j--){
                        if(w[j] && dict.contains(s.substring(j,i+1))){
                            w[i+1] = true;
                            break;
                        }
                    }
                }

            }
        }
        return w[size];

    }

    public static void main(String[] args) {
        Word_Break word_break = new Word_Break();
        Set<String> dict = new HashSet<String>();
        dict.add("abc");
        dict.add("d");
        boolean rst = word_break.wordBreak("abcd", dict);
        System.out.println(rst);
    }
}
